21:10 13.09.2021

☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘
2021 © Перевод ❤ ANDREY KOVALEV w.f.a. ALLY ❤
Без оборота на меня.
Никакие претензии не принимаются ни ныне, ни присно, ни во веки веков, аминь.
На вкус и цвет ─ приятеля нет.
☺Пусть эта дорога из жёлтого кирпича приведёт вас к успеху.☺
♫ Да отделятся зёрна от плевел. ♫
☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘☘

arXiv: 1803.01022v1 [quant-ph] 2 Mar 2018
Программирование квантовых компьютеров.
Использование автоматизации проектирования.

Матиас Зёкен Томас Хаенер Мартин Рёттелер
Mathias Soeken Thomas Haener Martin Roetteler

Лаборатория интегрированных систем, EPFL, Лозанна, Швейцария
Integrated Systems Laboratory, EPFL, Lausanne, Switzerland

Институт теоретической физики, ETH Zurich, Швейцария
Institute for Theoretical Physics, ETH Zurich, Switzerland

  Станция Q, QuArC, Исследование Microsoft, Редмонд, Вашингтон, США
 Station Q,   QuArC,   Microsoft Research,       Redmond,           WA,       USA

Знакомство.

Последние разработки в области квантового оборудования показывают, что системы,
содержащие более 50 физических кубитов, вполне достижимы.

В таком масштабе классическое моделирование больше не будет возможным и есть вероятность,
что такие квантовые устройства могут превзойти даже классические суперкомпьютеры
при выполнении конкретных задач.

С быстрым ростом числа кубитов и времени когерентности,
становится всё более сложной задачей компиляция квантовых программ.

Это влечет за собой перевод высокоуровневого описания квантового алгоритма,
в аппаратные операции низкого уровня, которые могут выполняться квантовым устройством.

Некоторые части вычислений всё ещё могут выполняться вручную
из ─ за отсутствия продуктивных методов.

Это, в свою очередь, может привести к недостаткам в конструкции,
что помешает программированию квантового компьютера.

В этой статье мы обсуждаем проблемы, связанные с полной автоматизацией квантовой компиляции.

Мы мотивируем направления будущих исследований, для решения этих проблем.

Тем не менее, с помощью алгоритмов и подходов, существующих сегодня,
мы демонстрируем, как автоматически выполнять поток квантового программирования,
от алгоритма к физическому квантовому компьютеру, в простом алгоритмическом тесте,
а именно проблеме скрытого сдвига.

Мы представляем и используем два потока инструментов, которые используют RevKit.

Один, основан на ProjectQ и предназначен для IBM Quantum Experience или локального симулятора
и один, основанный на квантовом языке программирования Microsoft Q#.

I ВСТУПЛЕНИЕ

С быстрым развитием квантового оборудования, квантовые компьютеры скоро достигнут размеров,
измеряемых количеством кубитов, на которых они работают,
что позволит им решать задачи,
недоступные для любого из лучших классических суперкомпьютеров.

Квантовые компьютеры получают это вычислительное преимущество перед классическими компьютерами
благодаря принципам суперпозиции состояний и интерференции вычислительных путей.

В отличие от этого, бит в обычных компьютерах, всегда находится в одном состоянии.

Линейно увеличивая количество кубитов, суперпозиция позволяет квантовым компьютерам экспоненциально
увеличивать свое вычислительное пространство и при этом
выполнять операции на этом экспоненциально большом пространстве
с низкой стоимостью, в конкретном понимании это означает, что при прочих равных условиях,
например, 17-кубитный квантовый компьютер,
в два раза мощнее 16-кубитного квантового компьютера.

В то время, как классические вероятностные вычисления, также позволяют получить доступ
к экспоненциально большому пространству, только с линейными ресурсами,
квантовый компьютер может использовать принцип интерференции,
который позволяет усилить или уменьшить вероятность вычислительных путей.

При правильном проектировании, квантовый алгоритм может сочетать в себе способность исследовать
экспоненциально много вычислительных путей, при низких затратах,
с возможностью отмены бесполезных путей таким образом, чтобы измерение оставшихся путей
показало ответ на интересную вычислительную проблему.

Уже сейчас найдено несколько квантовых алгоритмов, которые в вычислительном отношении
превосходят свои классические аналоги.

Наиболее заметным из них, возможно, является алгоритм Шора [1],
который позволяет разлагать целые числа на множители за полиномиальное время,
тогда как для классических вычислений не известно ничего лучше,
чем субэкспоненциальная верхняя граница [2].

Следовательно, алгоритм Шора может взломать криптографию с открытым ключом, которая основана
на предположении, что разложения на целые числа является сложной задачей.

Недавно были получены точные оценки затрат на реализацию
алгоритма Шора для факторизации [3] и эллиптической кривой dlog [4],
основанные на реализации и тестировании крупномасштабных сетей Тоффоли.

Помимо алгоритма Шора, существуют другие квантовые алгоритмы, которые играют важную роль
в научных приложениях, представляющих интерес.

Примеры содержат:

• Алгоритм поиска Гровера [5], который обеспечивает квадратично более быстрый поиск в
неструктурированных базах данных, если правильный элемент может быть продуктивно распознан предикатом,
например NP-завершение задач.

Это имеет значение для выбора параметров безопасности в постквантовом криптографическом мире.

Возможно, что удивительно, но оказывается, что накладные расходы, связанные с реализацией
задающего предиката обратимым способом, могут быть весьма существенными [6].

• Алгоритм HHL [7], который обеспечивает экспоненциальное ускорение
решения линейных уравнений.

Поиск практических вариантов использования алгоритма HHL остается сложной задачей,
а несколько реальных приложений, которые были найдены до сих пор [8], [9],
требуют больших накладных расходов из-за реализации классических подпрограмм,
которые решают проблему.

• Квантовое моделирование [10] ─ смотрите в, например [11], [12]
обзоры и ссылки на литературу ─ для продуктивного моделирования взаимодействий
на атомном уровне [13], [14],
позволяющих аппроксимировать поведение в медицине, органике и материаловедении [15], [16]
и имеет приложения для моделирования квантовых теорий поля [17].

Чтобы выполнить квантовый алгоритм на физическом квантовом компьютере,
алгоритм должен быть выражен в терминах элементарных квантовых операций,
которые могут быть поняты квантовым компьютером,
так же как классические компьютерные программы
должны быть выражены в терминах низкоуровневых машинных инструкций
для запуска на классическом компьютере.

Квантовые компиляторы это ─ программы,
которые принимают высокоуровневое описание квантового алгоритма
и отображают его, в так называемых квантовых схемах.

Квантовые схемы это ─ не физическая сущность,
а абстракция физических операций, которые могут быть выполнены
с кубитами физической системы [18].

Они представлены в виде последовательностей низкоуровневых квантовых операций.

Квантовые схемы можно рассматривать как "ассемблерный код" квантового компьютера,
в котором кубиты играют роль регистров.

Цель квантовых компиляторов ─ найти квантовую схему,
которая соответствует количеству доступных кубитов
и минимизирует количество квантовых операций.

Задача квантовых компиляторов состоит в том, чтобы
отобразить комбинационные неквантовые операции в квантовые схемы,
не превышая при этом ограничений ресурсов
из-за ограниченного числа кубитов.

Это сложная проблема,
а современные квантовые компиляторы
не обеспечивают приемлемого и достаточного решения.

В этом году квантовые вычисления совершили большой скачок, поскольку исследования
физических устройств переходят из академической среды в несколько компаний [19].

Microsoft, Google, IBM, Intel, Alibaba, а также быстрорастущие стартапы IonQ и Rigetti
инвестируют в создание первого масштабируемого квантового компьютера.

На сегодняшний день крупнейшими общедоступными полностью программируемыми
квантовыми компьютерами являются IBM с 17 кубитами [20] и Rigetti с 19 кубитами [21].

Недавно анонсированы квантовый компьютер Intel с 17 кубитами [22]
и квантовый компьютер IBM с объемом до 50 кубитов [23].

Быстрый прогресс в области квантовых вычислений и квантового моделирования
подчеркивает важность наличия надежных и безопасных цепочек инструментов
квантового программирования.

II КВАНТОВЫЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ

В последние годы было предложено несколько языков квантового программирования,
от императивных до функциональных,
от низкоуровневых до высокоуровневых [26].

Такие языки, как Quipper [27], ScaffCC/Scaffold [28], [29], Liquid|> [30], Wire [31], Quil [32], Q# [33], [34] и ProjectQ [35],
разрешают программировать квантовые компьютеры.

Quipper это ─ функциональный квантовый язык программирования со строгой типизацией, встроенный в Haskell;
Scaffold это ─ автономный Cи подобный язык программирования, а его компилятор ScaffCC использует платформу LLVM;
Qwire встроен в систему проверки Coq;
LIQUi | ⟩ встроен в F #;
Q#-это автономный язык, подобный F#, а
ProjectQ и Quil встроены в Python.

Все упомянутые языки предлагают расширяемые структуры для описания и манипулирования квантовыми схемами,
а некоторые из них предлагают методы декомпозиции врат и оптимизации схем,
некоторые ─ классические потоки управления и экспорт квантовых схем
для целей визуализации или оценки ресурсов.

Теоретически было бы достаточно, если бы язык программирования
для квантовых вычислений поддерживал набор элементов целевого оборудования.

1 в отличие от квантовых компьютеров специального назначения,
таких как квантовый аннеалер D-Wave.

Сходство между таким подходом и классическим языком ассемблера
привело к появлению квантовых языков ассемблера,
таких как QASM [36] и OPEN-QASM [37].

Хотя этого достаточно для современного квантового оборудования,
способного выполнять несколько операций с вентилями менее чем на 20 кубитах,
программирование на таком языке не является ни масштабируемым,
ни особенно удобным для пользователя.

Скорее, язык квантового программирования должен обеспечивать абстракции высокого уровня,
чтобы сократить время разработки и обеспечить переносимость в широком диапазоне бэкэндов
квантового оборудования, аналогично современным компиляторам
для классических языков высокого уровня, таких как C++.

В дополнение к чисто классическим и чисто квантовым подпрограммам,
типичные квантовые алгоритмы также требуют, чтобы классические функции

оценивались на основе суперпозиции входных данных например,
модульное возведение в степень в алгоритме Шора для разложения на множители [1].

Следовательно, такие “смешанные” конструкции также должны поддерживаться языком,
а компилятор должен иметь возможность переводить эти конструкции в инструкции,
которые могут выполняться квантовым оборудованием.

III ОСНОВЫ КВАНТОВЫХ ВЫЧИСЛЕНИЙ

В этом разделе представлены необходимые сведения о квантовых алгоритмах и квантовых схемах.
Это введение специально сокращено и сосредоточено на наиболее важных обозначениях и определениях,
которые необходимы в ходе этой статьи.
За более подробным обзором по этому вопросу, мы отсылаем читателя к стандартной литературе [38].

Квантовый алгоритм реализован в терминах квантовой программы,
которая представляет собой последовательность квантовых операций высокого уровня,
выполняемых над набором кубитов.

(α₀) Состояние кубита моделируется как вертикальный вектор |φ ⟩ = (α₁),
с двумя комплексными элементами α₀ и α₁,
называемыми амплитудами, такими как |α₀|² + |α₁|² = 1.

Значения |α₀|² и |α₁|² это ─ вероятности того, будет ли состояние кубита равно 0 или 1,
после его определения, соответственно.

Классическими состояниями для логического 0 и логической 1
являются |0 ⟩ = (₀) и |1 ⟩ = (₀), соответственно.

Следовательно, мы можем записать состояние кубита как |φ ⟩ = α₀|0 ⟩ +α₁|1>.

Обозначение |∙ ⟩ называется обозначением Дирака или скобкой
и типично для обозначения квантовых состояний.

Состояние, в котором результат измерения с равной вероятностью равен 0 или 1,
например, 1/√2 (₁), которое сокращенно обозначается |+ ⟩,
поскольку оно очень часто встречается при разработке квантовых алгоритмов.

Другое состояние с теми же вероятностями измерения |- ⟩ = 1/√2 (- ₁).

Хотя вероятность измерения одна и та же, квантовое состояние ─ нет, что является одной из причин,
по которой квантовые вычисления существенно отличаются от вероятностных вычислений.

Регистры кубитов относятся к квантовым состояниям, состоящим из нескольких кубитов.

В качестве примера, 2-х кубитный регистр представлен
состоянием (α₀₀ α₀₁ α₁₀ α₁₁) = α₀₀|00 ⟩ + α₀₁|01 ⟩ + α₁₀|10> + α₁₁|11 ⟩,
которая имеет четыре амплитуды, по одной для каждого классического
состояния |00 ⟩, |01 ⟩, |10 ⟩ и |11 ⟩.

В общем случае n-кбитовый регистр представляет собой
вертикальный вектор |φ ⟩ = ∑ α|b ⟩ с 2ⁿ амплитудами.

Это отражает экспоненциальную мощность кубитов.

Квантовые операции моделируются в терминах унитарных матриц,
называемых квантовыми воротами.

Матрица U является унитарной , если UU† =U†U = I,
где U† означает сопряженное транспонирование U,
также называемая Эрмитовой или сопряжённой U, а I это матрица идентичности.

Унитарная матрица сохраняет длину и поэтому отображает состояние одного кубита
в состояние другого кубита.

Рисунок 1: Некоторые основные примеры квантовых схем.
Схемы считываются слева направо.

На рисунке (а) показана простая квантовая схема, запутывающая два кубита.

Схема состоит из ворот Хадамард H и управляемых врат НЕ,
которые создают на входе |0 ⟩ |0 ⟩ результирующее выходное состояние |ψ ⟩ = 1/√2 (|00 ⟩ + |11 ⟩).

На (b) показан пример более крупной квантовой схемы,
состоящей из локальных циркуляций R1,..., R4, действующих на отдельные кубиты,
более крупных унитарных ворот U1, U2,
действующих на несколько кубитов и двух операций измерения,
применяемых к двум верхним кубитам.

Квантовая операция, действующая на один кубит, представляет собой унитарную матрицу 2 × 2,
а квантовая операция, действующая на регистр n-кубитов,
представляет собой унитарную матрицу 2 × 2.

Примером операции с одним кубитом является так называемая операция Хадамарда.

H = 1/√2 (₁¹ ⁻₁¹ ) .

Эта операция может быть использована для создания суперпозиции двух базовых состояний |0 ⟩ и |1 ⟩,
так как H|0 ⟩ = 1/√2 (|0 ⟩ + |1 ⟩).

Операция CNOT представляет собой 2-кубитную квантовую операцию, которая отображает
|φ₁ ⟩|φ₂ ⟩ → |φ₁ ⟩|φ₁ ⊕φ₂ ⟩,
где '⊕' — операция исключающее ИЛИ.

Операция CNOT инвертирует целевой кубит | φ₂ ⟩, если управляющий кубит φ₁ ⟩ равен 1.

Его можно представить в виде унитарной матрицы
(
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
)

Унитарная матрица операции CNOT является матрицей перестановок.

Квантовая операция, унитарная матрица которой является матрицей перестановок,
называется классической операцией.

Это также означает, что все классические операции должны быть обратимыми,
так как в противном случае они не могут быть представлены в терминах матрицы перестановок.

Квантовый алгоритм описывает взаимодействие квантовых операций с кубитами.
На рисунке 1(а) показано абстрактное представление такой квантовой схемы.
Горизонтальные линии представляют кубиты, коробки представляют квантовые операции,
которые взаимодействуют с кубитами, и время движется слева направо.

Следовательно, вертикальное направление соответствует пространству ─ космосу,
то есть количеству кубитов, а горизонтальное направление соответствует времени ─ такту,
то есть количеству квантовых операций.

Существует три типа операций:
i квантовые операции, это R1, . . . , R4 на рисунке,
ii классические операции, это U1 и U2 на рисунке и
iii измерения, которые показаны измерителем.

Классические операции выполняют классические вычисления, такие как
арифметические операции, но действуют на кубиты, а не на биты.

Отсутствие врат в схеме соответствует матрице идентичности.

На рисунке 1(б) показан простой квантовый алгоритм, состоящий из врат Хадармад,
за которыми следует операция CNOT.

Операция CNOT имеет специальную обозначение со сплошным кругом,
для управляющего кубита и символом " ⊕ " для целевого кубита.

Рисунок 2: Поток проектирования высокого уровня для сопоставления квантовых алгоритмов с квантовыми компьютерами.

Этот квантовый алгоритм принимает в качестве входных данных два кубита,
инициализированных в состоянии |0 ⟩ и создаёт 2-кубитное состояние 1/√2 (|00 ⟩+ |11 ⟩).

Это состояние запутано, то есть при измерении одного кубита немедленно определяется результат второго.
Это также означает, что точное состояние одного из кубитов не может быть описано индивидуально.

Последовательная композиция двух врат в квантовой схеме соответствует умножению матрицы,
а параллельная композиция врат соответствует получению произведения Кронекера, обозначаемого"⊕".

Унитарная матрица, представленная квантовой схемой на рисунке 1(b) — CNOT(H ⊕ I).

Обратите внимание, что современные квантовые алгоритмы
опираются на множество различных комбинационных вычислений.

Для разложения на множители требуется постоянная модульная арифметика [1],
для вычисления дискретных логарифмов эллиптической кривой с использованием
квантового алгоритма требуется общая модульная арифметика [4],
для алгоритма HHL требуются методы возвратно-поступательного движения и типа Ньютона [7],
алгоритмы усиления амплитуды нуждаются в реализациях для поиска и столкновения [5],
а алгоритмы квантового моделирования нуждаются в функциях адресации и индексации для разреженных матриц,
а также вычислении гамильтоновых членов на лету [11].

IV АВТОМАТИЗАЦИЯ КВАНТОВОГО ПРОЕКТИРОВАНИЯ: ОБЩИЙ ПОТОК

На рисунке 2 наглядно показан общий процесс программирования для квантовых компьютеров.
Для разработки квантового алгоритма учитываются возможности целевого квантового компьютера.
Квантовый алгоритм состоит из квантовых частей и классических комбинационных операций.

Квантовый алгоритм следует преобразовать в квантовую схему.

В то время как существуют автоматические и адекватные решения для преобразования квантовых частей,
не существует достаточных решений для автоматического преобразования комбинационных операций.

Реально, современный поток квантового программирования,
зависит от предопределённых библиотечных компонентов,
для которых существуют квантовые схемы, созданные вручную.

Такой ручной поток требует много времени, не гибок и не масштабируется.

Скорее, хотелось бы сформулировать квантовую программу на высоком уровне абстракции и иметь компилятор,
способный автоматически переводить всю схему,
даже если нет доступных библиотек, оптимизированных вручную.

Таким образом, крайне важно, чтобы язык квантового программирования,
используемый для выражения квантовой программы,
поддерживал подобный процесс проектирования.

V КОМПИЛЯЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

Перевод классических комбинационных операций в квантовые схемы
включает в себя обратимый логический синтез [39].

Из-за физических свойств квантовых состояний, все операции должны выполняться обратимым образом.

Современные подходы сначала создают обратимую логическую схему с обратимыми вратами,
которые являются булевыми абстракциями классических обратимых операций.

Другие методы преобразуют обратимые врата в квантовые схемы [40], [41], [42].

За последние 15 лет было предложено множество подходов к синтезу обратимой логики,
например [43], [44], [45], [46].

Принято различать алгоритмы обратимого синтеза на основе того, является ли логическая функция,
входящая в алгоритм, уже обратимой функцией или нет.

Для обратимой булевой функции f: Bⁿ → Bⁿ алгоритмы обратимого синтеза находят квантовую схему из n кубитов,
которая реализует унитарную U: | x ⟩ → | f (x) ⟩ . (1)

Для этой задачи было предложено несколько алгоритмов.
Они различаются в зависимости от представления f.

Большинство ранних алгоритмов ожидают, что f будет представлена в виде
таблицы истинности ─ смотрите например [43], [47], [48], [49], [50].

Явное представление таблицы истинности, ограничивает приложение большими функциями, то есть n > 20.

Были предложены альтернативные реализации, которые работают с символическими представлениями f,
например как двоичные диаграммы решений ─ BDD [46], [51] или проблемы логической выполнимости [52].

Эти подходы позволяют находить квантовые схемы также для некоторых булевых функций, которые намного больше.
Однако символьное представление функции, не всегда гарантирует компактное представление функции.

Тем не менее, основным недостатком таких алгоритмов обратимых функций является то,
что они требуют обратимой функции ввода,
что редко встречается в большинстве интересующих алгоритмов.

Второй класс алгоритмов обратимого синтеза рассматривает необратимые функции f : bⁿ → bᵐ в качестве входных данных.

Поскольку квантовая схема не может представлять необратимые функции,
f должна быть вложена в обратимую функцию.
Это может быть сделано явно или неявно.

В явном случае обнаруживается обратимая функция g : Bʳ → Bʳ такая, что
g(x1, . . . , xn, 0, . . . , 0) = (y1, . . . , ym, ym + 1, . . . , yr), (2)
если f(x1, . . . , xn) = (y1, . . . , ym).

Нахождение такого g, при котором r минимально, сложно coNP [53] и,
следовательно, не масштабируется до более крупных функций, хотя символические методы
могут помочь немного увеличить диапазон применимых функций [53], [54].

Встраивание, как в (2), называется внедрением на месте,
поскольку входные значения не восстанавливаются, после применения g.

В качестве примера было применено явное встраивание
с символьным обратимым логическим синтезом для нахождения на месте обратимых схем
для обратной функции 1/x до n = m = 16 цифр в x и r = 31 , смотрите [55].

Можно легко показать, что существует обратимая функция g с r = m+ n, выбрав g(x, y) = (x, y ⊕ f(x)) (3),
где x = x1, . . . , xn, y = y1, . . . , ym, и " ⊕ " относится
к побитовому применению операции XOR в этом случае.

Такое встраивание также называется встраиванием Беннетта.

Так называемые подходы обратимого синтеза на основе ESOP,
исключительной суммы продуктов, [56], [57], [58] находят обратимые схемы, которые реализуют (3).

Чтобы применить синтез на основе ESOP, необходимо найти 2х-уровневые выражения SOP
для каждого из m выходов в f , например смотрите [59], [60].

Такой подход может занять много времени и ограничить применение большими функциями.
В [55] синтез на основе ESOP был успешно применён до n = 25, для обратной функции.
Масштабируемые алгоритмы обратимого синтеза требуют дополнительных помогающих кубитов,
называемых вспомогательными.

Для необратимой булевой функции f: Bⁿ → Bᵐ они находят квантовую схему (n + m + k) кубитов,
которая реализует унитарную

U : |x ⟩|y ⟩|0ᵏ ⟩ → |x ⟩|y ⊕ f(x) ⟩|0ᵏ ⟩. (4)

Если k = 0, задача синтеза соответствует синтезу на основе ESOP,
но для k > 0 алгоритм синтеза может использовать k дополнительных кубитов
для хранения промежуточных вычислений.

Наиболее эффективные методы используют многоуровневые логические сетевые представления,
такие как BDDs [45], [61], [62], И-инверторные графики [63], [64],
графики XOR-большинства [55] или сети LUT [65].

Эти методы называются иерархическим обратимым логическим синтезом.

Промежуточные результаты, представленные внутренними узлами в соответствующих логических сетях,
выводятся на дополнительные кубиты.

Если в сети много внутренних узлов, требуется много вспомогательных устройств,
однако для обмена количеством кубитов для квантовых операций
могут быть использованы стратегии дробления [66] [67].

Одна из самых больших проблем в синтезе иерархической обратимой логики заключается в том,
что k является результатом алгоритма синтеза,
то есть определяется требованиями алгоритма для временного хранения.

Одной из самых больших проблем в синтезе обратимой логики,
является поиск алгоритмов обратимого синтеза, которые принимают k в качестве входного параметра
и гарантируют возврат квантовой схемы, удовлетворяющей требованиям к пространству-космосу.

VI ПОКАЗАТЕЛЬНЫЙ ПРИМЕР

В этом и следующих разделах мы используем пример проблемы скрытого сдвига для булевых функций,
чтобы проиллюстрировать полный процесс программирования квантового компьютера.

Для этой цели мы используем языки квантовых программирования ProjectQ [35] и Q# [33],
сопряженные с платформой квантовой компиляции RevKit [68].

ProjectQ и Q# позволяют высокоуровневое описание алгоритма с использованием нескольких метаконструкций
и позволяют взаимодействовать с физическим квантовым компьютером.

RevKit используется для автоматического перевода комбинационных частей квантового алгоритма
для задачи скрытого сдвига в квантовых вратах.

ProjectQ это ─ программная среда с открытым исходным кодом для квантовых вычислений
с модульной конструкцией компилятора, которая позволяет экспертам в предметной области
легко расширять его функциональные возможности.
Более того, эта модульность обеспечивает переносимость осуществлений квантовых алгоритмов.

В частности, после того, как алгоритм был реализован, его можно запускать
с использованием различных типов бэкэндов,
будь то программное обеспечение ─ симулятор, эмулятор, счётчик ресурсов и так далее
или аппаратного обеспечения ─ классического и/или квантового.

Q# [33] это масштабируемый, многопарадигмальный, предметно-ориентированный язык программирования
для квантовых вычислений от Microsoft.
Платформа Q# позволяет описывать, как выполняются инструкции на квантовых машинах.

Машины, которые могут быть настроены специальными способами,
включают множество различных уровней абстракции,
от различных симуляторов до реального квантового оборудования.

Q# это мультипарадигма,
поскольку он поддерживает функциональные и императивные стили программирования.
Q# масштабируем,
так как он позволяет создавать программы для настраиваемых машин различного размера,
от маленьких машин с несколькими сотнями кубитов,
до больших машин с миллионами кубитов.

Наконец, будучи полноценным автономным языком,
Q# позволяет программисту кодировать сложные квантовые алгоритмы,
предлагает обширные и информативные отчеты об ошибках
и позволяет выполнять различные задачи, такие как отладка, профилирование, о
ценка ресурсов и некоторые специальные задачи симуляции.

RevKit это платформа и библиотека C++ с открытым исходным кодом,
которая реализует большой набор обратимых алгоритмов синтеза, оптимизации и сопоставления.
По умолчанию RevKit выполняется как командная оболочка,
которая позволяет выполнять сценарии синтеза, комбинируя множество различных команд.

Например, последовательность команд

revgen --hwb 4; tbs; revsimp; rptm; tpar; ps -c (5)

генерирует обратимую функцию, описывающую 4-входную обратимую функцию скрытых взвешенных бит,
синтезирует её в обратимую схему, используя синтез на основе преобразования [43],
выполняет упрощение результирующей схемы,
отображает её во врата Clifford+T, используя отображение, описанное в [42],
оптимизирует счетчик T с помощью алгоритма T-par,
представленного в [69] и наконец, выводит статистику окончательной квантовой схемы.

Ко всем командам RevKit, предоставляемым оболочкой,
также можно получить доступ через интерфейс Python, например

revkit.revgen(hwb = 4)

для первой команды в (5).

Используя интерфейс Python, RevKit можно запустить из ProjectQ с помощью модуля projectq.libs.revkit.

A. Квантовый алгоритм: проблема скрытого булевого сдвига.

В качестве наглядного примера рассмотрим проблему скрытого сдвига для булевых функций [70].

В общем, проблема скрытого сдвига является вполне естественным источником проблем,
в которых квантовый компьютер может иметь преимущество перед классическим компьютером,
поскольку он использует свойство, заключающееся в том,
что быстрые свертки могут выполняться путем вычисления преобразований Фурье и точечного умножения.

В [71] смотрите общую информацию о скрытых сдвигах и связанных с ними проблемах,
а в [70] о случае скрытых сдвигов над булевыми функциями.

В последнее время задача скрытого сдвига для изогнутых функций была также изучена
в [72] с точки зрения классического моделирования получаемых квантовых схем.

Проблема вычисления скрытых сдвигов для булевых функций заключается в следующем:

Определение 1. Проблема скрытого сдвига:
Пусть n ≥ 1 и ƒ, g: Bⁿ → B

это две булевы функции такие, что выполняются следующие условия:
(i) ƒ и g ─ бент-функции и ii существуют s ∈ Bⁿ такие,
что g (x) = ƒ (x + s) для всех x ∈ Bⁿ.

Более того, пусть для g и двойственной бент-функции f дан доступ оракула.
Затем задача состоит в том, чтобы найти скрытый сдвиг s.

Бент-функции это ─ булевы функции, которые имеют совершенно плоский спектр Фурье, то есть Хадамард,
что в некотором смысле делает их похожими на случайный шум.

Рисунок 3: Квантовый алгоритм для задачи скрытого сдвига для бент-функции f.

Кроме того, алгоритму необходим доступ к двойной бент-функции f,
которая снова вычисляется в фазе через диагональную унитарную функцию.
Легко видеть, что бент-функции могут существовать только при чётном числе переменных n.

Что делает проблему скрытого сдвига для бент-функций привлекательной,
так это то, что можно показать, что классические алгоритмы не могут найти сдвиг продуктивно,
тогда как квантовые алгоритмы могут найти сдвиг только с 1 запросом к g и 1 запросом к f.

Более того, квантовый алгоритм для поиска скрытых сдвигов очень прост,
как показано на рисунке 3: необходимые врата это ─ врата Хадамард,
диагональные унитары для реализации сдвинутой функции
и двойной бент-функции, а также измерения в вычислительном базисе.

Привлекательной особенностью алгоритма является то, что при условии идеальных врат,
ответ является детерминированным, то есть измеренная-понятая битовая комбинация
напрямую соответствует скрытому сдвигу.

Мы присваиваем каждой операции в квантовом алгоритме индекс от 1 до 6,
написанный под каждыми вратами.

B. Бент-функции Майорана-МакФарланда

Возможно, наиболее простым примером бент-функции является скалярное произведение

ƒ(x, y) = xy ͭ = ∑ⁿᵢ₌₁ xᵢ yᵢ двух битовых векторов x = x₁,. . . , xₙ и y = y₁,. . . , уₙ.

Обратите внимание, что это булева функция f: B2n → B от чётного числа 2n переменных.

f(x, y) = xπ(y)t + h(y) (6)

для произвольной перестановки π ∈ S₂ⁿ на всех 2ⁿ логических битовых векторах длины n
и произвольной булевой функции h: Bⁿ → B.

Это приводит к классу так называемых бент-функций Майорана ─ МакФарланда.
Названые в честь математиков Джеймса А. Майорана (1946–2014)
и Роберта Л. МакФарланда, которые первыми изучили эти функции около 50 лет назад.

Двойственная бент-функция ƒ(x, y) = π⁻¹(x) yt + h (π⁻¹ (x)) [70].

Асимптотически размер этого класса масштабируется как O (2cn2 n),
что однако, является дважды экспоненциальным по n,
что является лишь экспоненциально малой частью набора всех булевых функций от 2n переменных.

Простой подсчёт аргументов показывает, что у большинства перестановок π нет продуктивной схемы,
однако существуют естественные семейства бент-функций Майорана-МакФарланда,
для которых перестановка π, а также булева функция h могут быть продуктивно реализованы.

Та же самая базовая схема, что показана на рисунке 3, может использоваться
для решения проблемы скрытого сдвига для бент-функций Майорана-МакФарланда.

Однако обратите внимание, что в отличие от случая функции скалярного произведения,
для которой выполняется f = f, для более общего случая,
когда π не является тождественной перестановкой,
диагональная унитарная Uf =∑x (— 1) f (x) | x ⟩ ⟨ x | реализующая бент-функцию f и сдвиг g
отличается от диагонального унитарного Uf = ∑x (—1) f? (x) | x ⟩ ⟨ x | реализации двойной бент-функции.

VII ВЗАИМОДЕЙСТВИЕ С PROJECTQ И СИМУЛЯТОРОМ / IBM BACKEND

В этом разделе мы покажем, как запрограммировать конкретный экземпляр проблемы скрытого сдвига
с помощью ProjectQ и RevKit.

Мы выбираем f(x) = x1 x2 ? x3 x4 в качестве булевой функции от 4 переменных, а g(x) = f(x + 1), то есть, s = 1.
Можно показать, что f = f? .

На рисунке 4 показан код Python проекта Q для этого примера.

Соответствующая квантовая схема, генерируемая этим кодом, показана на рисунке 5.

Строки 10 – 11 инициализируют движок ProjectQ с 4 кубитами, называемыми x1, x2, x3 и x4
и сохраняют их в списке кубитов.

Строка 15 выполняет шаг 1 квантового алгоритма, описанного на рисунке 3.

Строка 16 описывает сдвиг на s = 1, реализованный с помощью операции X на наименее значимом кубите x1.
Вместе с фазовой схемой, вычисляемой для f в строке 17, он вычисляет шаг 2 в квантовом алгоритме.

В качестве входных данных для оператора PhaseOracle мы можем предоставить предикат f,
реализованный как функция Python.
Оператор PhaseOracle преобразует код Python в f, в логическое выражение.
Это выражение затем передается в RevKit, который автоматически компилирует выражение в схему,
вычисляя функцию, описанную f, в глобальной фазе схемы.

Рисунок 5: Квантовая схема, реализованная кодом Python на рисунке 4;
индексы под строками соответствуют шагам на рисунке 3,
индексы над строками соответствуют строкам на рисунке 4.

Рисунок 6: Гистограмма, изображающая среднее значение и стандартное отклонение вероятностей исхода трёх прогонов кода на рисунке 4.

Каждый запуск состоит из 1024 выполнений схемы на микросхеме IBM Quantum Experience.
Корректный сдвиг s = 1 был найден со средней вероятностью p ≈ 0,63.
Оператор Uncompute в строке 18 отменяет вычисление всех операций,
указанных в блоке Compute в строках 14 – 16, применяя все операции в обратном порядке.
Это добавит в квантовую схему шаг 3 алгоритма.

Так как f? = f , мы снова вычисляем фазовую схему для f в строке 20, применяем затворы Hadamard
к каждому кубиту для шага 5 алгоритма и наконец,
измеряем-понимаем все кубиты в строке 22.

Результирующее состояние кубитов, вычисленное с помощью моделирования, соответствует сдвигу s = 1.
Программа выводит "Сдвиг равен 1".

Выполнение этого и трёхкратное выполнение 1024 снимков схемы дало результаты,
показанные на рисунке 6. На рисунке 7 показан код Python, который реализует экземпляр задачи скрытого сдвига для бент-функции Майорана-МакФарланда,
где n = 3, π = [0, 2, 3, 5, 7, 1, 4, 6] и h = 0.
На рисунке 8 показана соответствующая схема.
Программа аналогична программе на рисунке 4.

Мы создаем 6 кубитов и разделяем их на три кубита x для x1, x2, x3 и три кубита y для y1, y2, y3.
Внутренний продукт реализуется с помощью функции bent, заданной функцией Python f.

Рисунок 7. Код Python в ProjectQ для примера проблемы скрытого сдвига,
когда f (x, y) = xpi (y) t, pi = [0, 2, 3, 5, 7, 1, 4, 6] и s = 5.

Мы используем функцию PermutationOracle, чтобы создать квантовую схему из перестановки,
которая затем применяется к кубитам в x.

Функция PermutationOracle вызывает RevKit с помощью синтеза на основе преобразования [43]
с последующим отображением врат Тоффоли во врата Клиффорда+Т
с помощью алгоритма, представленного в [42].

Для второй части схемы нам понадобится квантовая схема обратной перестановки pi? 1.

Вместо того, чтобы инвертировать число Пи, мы вычисляем другую квантовую схему для числа Пи
и инвертируем схему, используя оператор Dagger.
Обратите внимание, что для этой компиляции мы выбрали синтез на основе разложения [47]
для поиска сети Тоффоли для перестановки.

Поскольку каждая перестановка не вычисляется после фазовой схемы для внутреннего произведения,
окончательная схема состоит из четырех подсхем, реализующих либо число пи, либо его обратное.
Они выделены пунктирными прямоугольниками на рисунке 8.

VIII ВЗАИМОДЕЙСТВИЕ С Q# И СЕРВЕРНОЙ ЧАСТЬЮ СИМУЛЯТОРА

Далее мы описываем поток программирования, который реализует тот же высокоуровневый алгоритм,
то есть экземпляр проблемы скрытого сдвига для функций Майорана-МакФарланда, но реализует его на Q#.

Хотя на высоком уровне взаимодействие между RevKit и Q# происходит так, как описано на рисунке 2,
фактический вызов RevKit в потоке проектирования
немного отличается от взаимодействия RevKit/ProjectQ в том,
что RevKit используется в качестве препроцессора
для создания кода оракула перестановок в виде собственного кода Q#.

Впоследствии компилятор Q# затем вызывается для компиляции алгоритма и нацеливания на серверную часть симулятора,
которая является частью набора для разработки Microsoft Quantum ─ QDK.

Код для задачи скрытого сдвига, показанный на рисунке 9,
структурно очень похож на знакомые языки, такие как C# и Java, в использовании точки с запятой для конечных операторов,
фигурных скобок для операторов группы и двойной косой черты для введения комментариев.

Q# использует пространства названий, для группировки определений
и разрешает ссылки на элементы из других пространств названий.
Код Q# начинается с оператора пространства названий, строка 1, который объявляет символы
и делает их доступными для других проектов.

Механизм включения других пространств названий осуществляется с помощью ключевого слова open.
Здесь оно используется в строке 3 для включения основных врат, таких как врата Hadamard H
и в строке 5 для включения canon,
которое представляет собой большую библиотеку полезных операций, функций и комбинаторов.

Для текущего примера мы используем операции ApplyToEach и MResetZ из canon.

Реализация самого оракула перестановок предусмотрена в другом пространстве названий,
которое включено в строку 7.
Базовой единицей в Q# для моделирования побочных результатов квантовых данных является операция,
такая как операция HiddenShift, объявленная в строке 9.
Помимо операций, Q# также поддерживает функции, которые позволяют изменять состояние,
которое является чисто классическим.

Обратите внимание, что определение операции или функции должно начинаться с объявления подписи типа функции,
включая её входные и выходные типы.
Это делается в строках 10 - 14 настоящего примера.

Операции и функции являются первоклассными гражданами в Q#, то есть,
они могут передаваться в качестве аргументов.
В данном случае Ustar является операцией, реализуемой диагональным оператором Uf?
как определено ранее.

Если операция изменяет состояние квантового регистра,
смоделированного здесь как массив Qubit[],
то его типом является Qubit[] = ⟩ (),
где () обозначает тип единицы.

Операции это ─ единственный способ манипулировать состоянием абстрактной модели квантовой машины.

Q# может использоваться для ориентирования на многие абстрактные модели квантовых машин,
включая будущие физические реализации масштабируемых квантовых компьютеров.

В настоящее время основной целью Q# является современный симулятор,
который может легко обрабатывать до 30 кубитов на стандартном компьютере
и более 40 кубитов на распределённом компьютере с использованием реализации на основе MPI.

Элемент body в строке 15 определяет выполнение операции.

Операции Q# также могут указывать реализации для вариантов или производных операций,
которые распространены в квантовых вычислениях.

Эти варианты обозначаются сопряженным ─ обратным, контролируемым и контролируемым сопряжением.

Если задано ключевое слово auto,
то компилятор автоматически вычисляет обратную или управляемую версию операции на основе тела,
но в целом может иметь смысл предоставить эти реализации отдельно,
поскольку могут быть известны более результативные схемы.

Рисунок 8: Квантовая схема, которая реализуется кодом Python на рисунке 7.
Пунктирными прямоугольниками выделены подсхемы,
которые соответствуют реализациям числа пи и его обратного.

Рисунок 9: Реализация алгоритма корреляции для логической задачи скрытого сдвига в Q#.
Этот код поставляется в качестве образца алгоритма вместе с Microsoft SDK [33].

Хотя варианты не встречаются в реализации операции HiddenShift,
они встречаются в реализации операции PermutationOracle ниже.
Q# позволяет ввести изменяемую переменную, как в строке 16, которая возвращается в программу драйвера,
которая может быть записана на языке .NET, таком как C# или F#, в строке 30.

Другими примечательными элементами, используемыми в этом фрагменте кода,
являются выделение чистых кубитов, которые по определению инициализируются в состояние |0? ,
в строке 18 с помощью ключевого слова using.
Q# предлагает классические конструкции потока и управления,
как в строке 25, где код перебирает диапазон целых чисел, используя for.

Наконец, мы отмечаем, что Q# поддерживает изменяемые и неизменяемые типы.
Синтаксис объявления новой изменяемой переменной показан в строке 16 массива,
в котором будет содержаться конечный результат вычисления.
Присвоение изменяемых переменных выполняется с помощью операторов set, как в строке 26.

Рисунок 10: Код Q# для примера задачи скрытого сдвига, где f(x, y) = xpi(y)t, pi = [0, 2, 3, 5, 7, 1, 4, 6].

Определение экземпляра Ug и Uf? самой проблемы скрытого сдвига
выполняется путём вызова Rev Kit сначала в состоянии предварительной обработки.
Входными данными для этого является описание перестановки pi,
которая должна быть реализована. Выходом этого этапа является другая программа Q#,
которая показана как операция PermutationOracle на рисунке 10.

Обратите внимание, что в этой операции используются примитивные врата,
встроенные в язык Q# и являющиеся родными для базовой абстрактной модели квантовой машины,
такие как H, T и CNOT.
Также обратите внимание, что функтор Adjoint используется в строках 18, 20 и 21,
которые вычисляют обратную величину вызываемой операции.

Экземпляр изогнутой функции определяется в блоке, начинающийся в строке 48
и возвращает функцию с сигнатурой Qubit[] = ⟩ ().


Реализация этой функции, которая зависит от количества переменных,
здесь обозначается целым числом n с использованием примитивного типа Int,
вызывает другую операцию, из которой функция строится с использованием частичного применения,
что является основным механизмом, в котором, например каррирование может быть реализовано в Q#.

Из-за недостатка места не все подпрограммы, используемые в реализации смещенных бент-функций и тестовой оснастки,
показаны в виде фрагментов, однако их можно проверить как образец кода Q#,
который был поставлен с QDK [33].
Подпрограмма тестирования состоит из части C#, которая вызывает указанную выше программу Q#
и нацелена на встроенный симулятор.

IX ПРОБЛЕМЫ И ВЫВОДЫ

В этой статье мы проиллюстрировали и обсудили процесс проектирования высокого уровня для отображения
квантового алгоритма на квантовые компьютеры с использованием языков квантового программирования.

Выразительные синтаксические конструкции и богатый API,
в сочетании с результативными алгоритмами автоматической компиляции,
позволяют нам выражать квантовые алгоритмы на высоком уровне,
не обременяя себя определением каждой отдельной квантовой операции.

Это в конечном итоге приводит к реализации
i более масштабируемых алгоритмов,
поскольку утомительная ручная компиляция комбинационных компонентов выполняется автоматически и
ii более сложных алгоритмов
путём объединения абстрактных синтаксических конструкций высокого уровня,
предлагаемых языком программирования.

Таким образом, программирование квантовых компьютеров догоняет своего классического аналога,
в котором множество языков программирования высокого уровня
и значительные усилия по разработке компиляторов делают ненужными описания ручной сборки.

Несколько проблем остаются нерешёнными и ожидают достаточных решений.

В этой статье мы рассмотрели только простые обратимые методы синтеза,
которые не требуют дополнительных вспомогательных кубитов для реализации квантовой схемы.
Это ограничивает их применение небольшими функциями с примерно 25 переменными.
Для автоматической компиляции более крупных функций,
методы обратимого логического синтеза требуют дополнительных кубитов.
Они обычно определяются во время выполнения алгоритма и не могут быть связаны заранее.

Методы синтеза, которые находят решение без превышения заданного числа вспомогательных элементов,
встречаются редко и состояние доступных решений всё ещё находится в зачаточном состоянии [65], [67].

Другой проблемой является проверка синтезированных схем.

Моделирование квантовой схемы может потребовать представления полного квантового состояния,
которое экспоненциально велико по числу кубитов.

Проверенные компиляторы, которые являются “корректными по конструкции”, решают эту проблему [73].

Однако при применении пост-оптимизации необходимо убедиться,
что оптимизированная схема не изменила функциональность, требуя моделирования полных квантовых состояний,
в худшем случае.

БЛАГОДАРНОСТИ

Благодарим команду QuArC за полезные обсуждения.

Схемы были набраны с использованием ⟨q|pic⟩ Тома Дрейпера Tom Draper и Сэнди Кутина Sandy Kutin.

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА

[1] П. У. Шор,
“Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере”,
Журнал SIAM по вычислительной технике, том 26, № 5, стр. 1484-1509, 1997.
[1] P. W. Shor,
“Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,”
SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, 1997.

[2] С. Померанс,
“Повесть о двух сетчатых фильтрах", Заметки AMS, том 43, № 12, стр. 1473-1485, 1996.
[2] C. Pomerance,
“A tale of two sieves,” Notices of the AMS, vol. 43, no. 12, pp. 1473–1485, 1996.

[3] Т. Хёнер, М. Реттелер и К. М. Своре,
“Факторинг с использованием 2n+2 кубитов с модульным умножением на основе Тоффоли",
Квантовая информация и вычисления, том 18, № 7 и 8, стр. 673-684, 2017.
[3] T. Häner, M. Roetteler, and K. M. Svore,
“Factoring using 2n+2 qubits with Toffoli based modular multiplication,”
Quantum Information and Computation, vol. 18, no. 7&8, pp. 673–684, 2017.

[4] М. Реттелер, М. Наэриг, К. Свор и К. Лаутер,
“Квантовые оценки ресурсов для вычисления дискретных логарифмов эллиптической кривой”,
в материалах 23-й ежегодной Международной конференции по теории
и Приложения криптологии и информационной безопасности (ASIACRYPT’17),
Хонг Кинг, Китай,
сер. Конспекты лекций по информатике, том 10625. Спрингер, 2017, стр. 241-270.
[4] M. Roetteler, M. Naehrig, K. Svore, and K. Lauter,
“Quantum resource estimates for computing elliptic curve discrete logarithms,”
in Proceedings of the 23rd Annual International Conference on the Theory
and Applications of Cryptology and Information Security (ASIACRYPT’17),
Hong King, China,
ser. Lecture Notes in Computer Science, vol. 10625. Springer, 2017, pp. 241–270.

[5] Л. К. Гровер,
“Быстрый квантово-механический алгоритм поиска в базе данных”,
Симпозиум по теории и вычислительной технике, 1996, стр. 212-219.
[5] L. K. Grover,
“A fast quantum mechanical algorithm for database search,”
in Symposium on Theory and Computing, 1996, pp. 212–219.

[6] М. Грассл, Б. Лангенберг, М. Реттелер и Р. Штайнвандт,
“Применение алгоритма Гровера к aes: оценки квантовых ресурсов”,
в Международной конференции по постквантовой криптографии,
сер. Конспекты лекций по информатике, том 9606. Спрингер, 2016, стр. 29-43.
[6] M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt,
“Applying Grover’s algorithm to aes: quantum resource estimates,”
in Int’l Conf. on Post-Quantum Cryptography,
ser. Lecture Notes in Computer Science, vol. 9606. Springer, 2016, pp. 29–43.

[7] А. У. Харроу, А. Хасидим и С. Ллойд,
“Квантовый алгоритм для линейных систем уравнений”,
Физические обзоры писем, том 103, № 15, стр. 150502, 2009.
[7] A. W. Harrow, A. Hassidim, and S. Lloyd,
“Quantum algorithm for linear systems of equations,”
Physical Review Letters, vol. 103, no. 15, p. 150502, 2009.

[8] Б. Д. Клэйдер, Б. С. Джейкобс и К. Р. Спрауз,
“Алгоритм квантовой линейной системы с предварительными условиями",
Физические обзоры писем, том 110, № 25, стр. 250504, 2013.
[8] B. D. Clader, B. C. Jacobs, and C. R. Sprouse,
“Preconditioned quantum linear system algorithm,”
Physical Review Letters, vol. 110, no. 25, p. 250504, 2013.

[9] А. Шерер, Б. Валирон, С. Мау, Д. С. Александер, Э. ван ден Берг и Т. Е. Чапуран,
“Анализ конкретных ресурсов алгоритма квантовой линейной системы,
используемого для вычисления поперечного сечения электромагнитного рассеяния двумерной цели",
Квантовая обработка информации, том 16, № 3, стр. 60, 2017.
[9] A. Scherer, B. Valiron, S. Mau, D. S. Alexander, E. van den Berg, and T. E. Chapuran,
“Concrete resource analysis of the quantum linearsystem algorithm
used to compute the electromagnetic scattering cross section of a 2D target,”
Quantum Information Processing, vol. 16, no. 3, p. 60, 2017.

[10] Р. П. Фейнман,
“Моделирование физики с помощью компьютеров”,
Международный журнал теоретической физики, том 21, стр. 467-488, 1982.
[10] R. P. Feynman,
“Simulating physics with computers,”
International Journal of Theoretical Physics, vol. 21, pp. 467–488, 1982.

[11] Т. Х. Джонсон, С. Р. Кларк и Д. Якш,
“Что такое квантовый симулятор?”
Квантовая технология EPJ, том 1, № 10, стр. 1-12, 2014.
[11] T. H. Johnson, S. R. Clark, and D. Jaksch,
“What is a quantum simulator?”
EPJ Quantum Technology, vol. 1, no. 10, pp. 1–12, 2014.

[12] Д. У. Берри, А. М. Чайлдс и Р. Котари,
“Гамильтоново моделирование с почти оптимальной зависимостью от всех параметров”,
на 56-м ежегодном симпозиуме IEEE по основам компьютерных наук,
FOCS 2015, 2015, стр. 792–809.
[12] D. W. Berry, A. M. Childs, and R. Kothari,
“Hamiltonian simulation with nearly optimal dependence on all parameters,”
in IEEE 56th Annual Symposium on Foundations of Computer Science,
FOCS 2015, 2015, pp. 792–809.

[13] А. Аспуру-Гузик, А. Д. Дутой и М. Лав, Питер Дж. и Хед-Гордон,
“Имитационное квантовое вычисление молекулярных энергий",
Наука, том 309, стр. 1704-1707, 2005.
[13] A. Aspuru-Guzik, A. D. Dutoi, and M. Love, Peter J.and Head-Gordon,
“Simulated quantum computation of molecular energies,”
Science, vol.309, pp. 1704–1707, 2005.

[14] Д. Веккер, М. Б. Хастингс, Н. Вибе, Б. К. Кларк, С. Наяк и М. Тройер,
“Решение сильно коррелированных электронных моделей на квантовом компьютере”,
Физический обзор A, том 92, стр. 062318, 2015.
[14] D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer,
“Solving strongly correlated electron models on a quantum computer,”
Physical Review A, vol. 92, p. 062318, 2015.

[15] Р. Сомма, Г. Ортис, Дж. Э. Губернатис, Э. Книлл и Р. Лафламм,
“Моделирование физических явлений с помощью квантовых сетей",
Physical Review A, том 65, стр. 04323, 2002.
[15] R. Somma, G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme,
“Simulating physical phenomena by quantum networks,”
Physical Review A, vol. 65, p. 04323, 2002.

[16] Б. Бауэр, Д. Веккер, А. Дж. Миллис, М. Б. Хастингс и М. Тройер,
“Гибридный квантово-классический подход к коррелированным материалам”,
Физический обзор X, том 6, стр. 031045, 2016.
[16] B. Bauer, D. Wecker, A. J. Millis, M. B. Hastings, and M. Troyer,
“Hybrid quantum-classical approach to correlated materials,”
Physical Review X, vol. 6, p. 031045, 2016.

[17] С. П. Джордан, К. С. М. Ли и Дж. Прескилл,
“Квантовые алгоритмы для квантовых теорий поля”,
Наука, том 336, стр. 1130-1133, 2012.
[17] S. P. Jordan, K. S. M. Lee, and J. Preskill,
“Quantum algorithms for quantum field theories,”
Science, vol. 336, pp. 1130–1133, 2012.

[18] Ф. Т. Чонг, Д. Франклин и М. Мартоноси,
“Языки программирования и дизайн компиляторов для реалистичного квантового оборудования",
Nature, том 549, № 7671, стр. 180-187, 2017.
[18] F. T. Chong, D. Franklin, and M. Martonosi,
“Programming languages and compiler design for realistic quantum hardware,”
Nature, vol. 549, no. 7671, pp. 180–187, 2017.

[19] Д. Кастельвекки,
“Квантовые компьютеры, готовые выскочить из лаборатории в 2017 году”,
Nature, том 541, № 7635, стр. 9-10, 2017.
[19] D. Castelvecchi,
“Quantum computers ready to leap out of the lab in 2017,”
Nature, vol. 541, no. 7635, pp. 9–10, 2017.

[20] IBM,
“IBM создает свои самые мощные универсальные процессоры квантовых вычислений",
2017, пресс-релиз IBM, опубликованный в Интернете 17 мая 2017 года.
[20] IBM,
“IBM builds its most powerful universal quantum computing processors,” 2017,
press release by IBM, posted online May 17, 2017.

[21] Ригетти,
“Неконтролируемое машинное обучение на Rigetti 19Q с Forest1.2",
2017, пресс-релиз компании Rigetti, Inc., опубликованный в Интернете 18 декабря 2017 года.
[21] Rigetti,
“Unsupervised machine learning on Rigetti 19Q with Forest1.2,”
2017, press release by Rigetti, Inc., posted online December 18, 2017.

[22] Intel,
“Intel поставляет 17-кубитный сверхпроводящий чип с усовершенствованной упаковкой для QuTech",
2017, пресс-релиз Intel, опубликованный в Интернете 10 октября 2017 года.
[22] Intel,
“Intel delivers 17-qubit superconducting chip with advanced packaging to QuTech,”
2017, press release by Intel, posted online October 10, 2017.

[23] IBM,
“IBM объявляет о продвижении Квантовые системы и экосистема IBM”,
2017, пресс-релиз IBM, опубликованный в Интернете 10 ноября 2017 года.
[23] IBM,
“IBM announces advances to IBM quantum systems & ecosystem,”
2017, press release by IBM, posted online Nov 10, 2017.

[24] Э. Педно, Дж. А. Ганнелс, Г. Нанничини, Л. Хореш, Т. Магерлейн, Э. Соломоник и Р. Висниефф
“Преодоление барьера из 49 кубитов при моделировании квантовых схем",
препринт arXiv arXiv:1710.05867, 2017.
[24] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff,
“Breaking the 49-qubit barrier in the simulation of quantum circuits,”
arXiv preprint arXiv:1710.05867, 2017.

[25] Т. Хенер и Д. С. Штайгер,
“Моделирование 45-кубитной квантовой схемы на 0,5 петабайта”,
в Международной конференции по высокопроизводительным вычислениям,
сетям, хранению и анализу,
2017, стр. 33:1-33:10.
[25] T. Häner and D. S. Steiger,
“0.5 petabyte simulation of a 45-qubit quantum circuit,”
in Int’l Conf. on High Performance Computing, Networking, Storage and Analysis,
2017, pp. 33:1–33:10.

[26] J. Мищак,
“Модели квантовых вычислений и языки квантового программирования",
Булл. Пол. Акад. наук.-техн. наук., том 59, № 3, с. 305-324, 2011.
[26] J. Miszczak,
“Models of quantum computation and quantum programming languages,”
Bull. Pol. Acad. Sci.-Tech. Sci., vol. 59, no. 3, pp. 305–324, 2011.

[27] А. Грин, П. Л. Лумсдейн, Н.Росс, П. Селингер и Б. Валирон
“Quipper: масштабируемый квантовый язык программирования”,
на конференции ACM SIGPLAN по разработке и реализации языков программирования,
PLDI ’13, Сиэтл, Вашингтон, США, 16-19 июня 2013 г., 2013, стр. 333-342.
[27] A. Green, P. L. Lumsdaine, N. Ross, P. Selinger, and B. Valiron,
“Quipper: A scalable quantum programming language,”
in ACM SIGPLAN Conference on Programming Language Design and Implementation,
PLDI ’13, Seattle, WA, USA, June 16-19, 2013, 2013, pp. 333–342.

[28] А. Джавадиабхари, С. Патил, Д. Кудроу, Дж. Хеки, А. Львов, Ф. Т. Чонг и М. Мартоноси
“Scaffcc: Масштабируемая компиляция и анализ квантовых программ”,
Параллельные вычисления, том 45, стр. 2-17, 2015.
[28] A. JavadiAbhari, S. Patil, D. Kudrow, J. Heckey, A. Lvov, F. T. Chong, and M. Martonosi,
“Scaffcc: Scalable compilation and analysis of quantum programs,”
Parallel Computing, vol. 45, pp. 2–17, 2015.

[29] Дж. Хеки, С. Патил, А. Джавадиабхари, А. Холмс, Д. Кудроу, К. Р. Браун, Д. Франклин, Ф. Т. Чонг и М. Мартоноси
“Управление компилятором связи и параллелизма для квантовых вычислений",
в Материалах Двадцатой Международной конференции по архитектурной поддержке языков
программирования и операционных систем,
ASPLOS ’15, Стамбул, Турция, 14-18 марта 2015 г. ACM, 2015, стр. 445-456.
[29] J. Heckey, S. Patil, A. JavadiAbhari, A. Holmes, D. Kudrow, K. R. Brown, D. Franklin, F. T. Chong, and M. Martonosi,
“Compiler management of communication and parallelism for quantum computation,”
in Proceedings of the Twentieth International Conference on Architectural Support
for Programming Languages and Operating Systems,
ASPLOS ’15, Istanbul, Turkey, March 14-18, 2015. ACM, 2015, pp. 445–456.

[30] Д. Веккер и К. М. Своре
“LIQUi| ⟩: Архитектура проектирования программного обеспечения
и специфичный для предметной области язык
для квантовых вычислений”, 2014.
[30] D. Wecker and K. M. Svore,
“LIQUi| ⟩: A software design architecture and
domain-specific language for quantum computing,” 2014.

[31] Дж. Пайкин, Р. Рэнд и С. Зданцевич,
"QWIRE: основный язык для квантовых схем,"
в Статьях 44-ой Симпозиума ACM SIGPLAN по принципам языков программирования,
POPL 2017, Париж, Франция, 18-20 января 2017 года, 2017, стр. 846–858.
[31] J. Paykin, R. Rand, and S. Zdancewic,
“QWIRE: a core language for quantum circuits,”
in Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages,
POPL 2017, Paris, France, January 18-20, 2017, 2017, pp. 846–858.

[32] Р. С. Смит, М. Дж.Кертис и У. Дж. Цзэн
“Архитектура практического квантового набора инструкций”,
2016, arXiv: 1608.03355.
[32] R. S. Smith, M. J. Curtis, and W. J. Zeng,
“A practical quantum instruction set architecture,”
2016, arXiv: 1608.03355.

[33] “Набор для разработки Microsoft Quantum”, 2017, доступен по адресу https://microsoft.com/quantum.
[33] “Microsoft Quantum Development Kit,” 2017, available at https://microsoft.com/quantum.

[34] К. Своре, А. Геллер, М. Тройер, Дж. Азария, С. Гранаде, Б. Хейм, В. Ключников, М. Михайлова, А. Пас и М. Реттелер
“Q#: Обеспечение масштабируемых квантовых вычислений и разработки с помощью DSL высокого уровня”,
в материалах Семинара по языкам, специфичным для предметной области реального мира
(RWDSL 2018). ACM, 2018, стр. 7:1-7:10.
[34] K. Svore, A. Geller, M. Troyer, J. Azariah, C. Granade, B. Heim, V. Kliuchnikov, M. Mykhailova, A. Paz, and M. Roetteler,
“Q#: Enabling scalable quantum computing and development with a high-level DSL,”
in Proceedings of the Real World Domain Specific Languages Workshop
(RWDSL 2018). ACM, 2018, pp. 7:1–7:10.

[35] Д. С. Штайгер, Т. Хенер и М. Тройер
“ProjectQ: Программная платформа с открытым исходным кодом для квантовых вычислений",
препринт arXiv arXiv:1612.08091, 2016.
[35] D. S. Steiger, T. Haener, and M. Troyer,
“ProjectQ: An open source software framework for quantum computing,”
arXiv preprint arXiv:1612.08091, 2016.

[36] К. М. Своре, А. В. Ахо, А. В. Кросс, И. Чжуан и И. Л. Марков
“Многоуровневая архитектура программного обеспечения
для инструментов проектирования квантовых вычислений”,
Компьютер IEEE, том 39, № 1, стр. 74-83, 2006.
[36] K. M. Svore, A. V. Aho, A. W. Cross, I. Chuang, and I. L. Markov,
“A layered software architecture for quantum computing design tools,”
IEEE Computer, vol. 39, no. 1, pp. 74–83, 2006.

[37] А. У. Кросс, Л. С. Бишоп, Дж. А. Смолин и Дж. М. Гамбетта
“Открытый язык квантового ассемблера",
препринт arXiv arXiv:1707.03429, 2017.
[37] A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta,
“Open quantum assembly language,”
arXiv preprint arXiv:1707.03429, 2017.

[38] М. А. Нильсен и И. Л. Чжуан
Квантовые вычисления и квантовая информация.
Издательство Кембриджского университета, 2000.
[38] M. A. Nielsen and I. L. Chuang,
Quantum Computation and Quantum Information.
Cambridge University Press, 2000.

[39] М. Саеди и И. Л. Марков
“Синтез и оптимизация обратимых схем ─ обзор",
ACM Computing Surveys, том 45, № 2, стр. 21:1– 21:34, 2013.
[39] M. Saeedi and I. L. Markov,
“Synthesis and optimization of reversible circuits ─ a survey,”
ACM Computing Surveys, vol. 45, no. 2, pp. 21:1– 21:34, 2013.

[40] А. Баренко, К. Х. Беннетт, Р. Клив, Д. П. Дивинченцо, Н. Марголус, П. Шор, Т. Слитор, Дж. А. Смолин и Х. Вайнфуртер
“Элементарные ворота для квантовых вычислений”,
Физический обзор A, том 52, № 5, стр. 3457, 1995.
[40] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter,
“Elementary gates for quantum computation,”
Physical Review A, vol. 52, no. 5, p. 3457, 1995.

[41] Н. Абдессайд, М. Эми, М. Сокен и Р. Дрехслер
“Технологическое сопоставление обратимых схем с квантовыми схемами Клиффорда+Т”,
в Международной симпозиуме по многозначной логике, 2016, стр.150-155.
[41] N. Abdessaied, M. Amy, M. Soeken, and R. Drechsler,
“Technology mapping of reversible circuits to Clifford+T quantum circuits,”
in Int’l Symp. on Multiple-Valued Logic, 2016, pp. 150–155.

[42] Д. Маслов
“Преимущества использования врат Тоффоли с относительной фазой
с применением оптимизации Тоффоли с множественным управлением”,
Физический обзор A, том 93, стр. 022311, 2016.
[42] D. Maslov,
“Advantages of using relative-phase Toffoli gates
with an application to multiple control Toffoli optimization,”
Physical Review A, vol. 93, p. 022311, 2016.

[43] Д. М. Миллер, Д. Маслов и Г. В. Дуэк
“Алгоритм, основанный на преобразовании для синтеза обратимой логики",
на конференции по автоматизации проектирования,
2003, стр. 318-323.
[43] D. M. Miller, D. Maslov, and G. W. Dueck,
“A transformation based algorithm for reversible logic synthesis,”
in Design Automation Conference,
2003, pp. 318–323.

[44] В. В. Шенде, А. К. Прасад, И. Л. Марков и Дж. П. Хейс
“Синтез обратимых логических схем",
IEEE Trans. о САПР интегральных схем и систем, том 22, № 6,
стр. 710-722, 2003.
[44] V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes,
“Synthesis of reversible logic circuits,”
IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 22, no. 6, pp. 710–722, 2003.

[45] Р. Вилле и Р. Дречслер
“Синтез обратимой логики на основе BDD для больших функций",
Конференция по автоматизации проектирования, 2009, стр. 270-275.
[45] R. Wille and R. Drechsler,
“BDD-based synthesis of reversible logic for large functions,”
in Design Automation Conference, 2009, pp. 270–275.

[46] М. Сокен, Р. Вилле, С. Хилкен, Н. Пшигода и Р. Дрехслер
“Синтез обратимых схем с минимальными линиями для больших функций”,
Конференция по автоматизации проектирования
в Азии и Южной части Тихого океана, 2012, стр. 85-92.
[46] M. Soeken, R. Wille, C. Hilken, N. Przigoda, and R. Drechsler,
“Synthesis of reversible circuits with minimal lines for large functions,”
in Asia and South Pacific Design Automation Conference, 2012, pp. 85–92.

[47] А. Де Вос и Ю. Ван Рентергем
“Подгруппы Юнга для реверсивных компьютеров",
Достижения в области математики коммуникаций, том 2, № 2, стр. 183-200, 2008.
[47] A. De Vos and Y. Van Rentergem,
“Young subgroups for reversible computers,”
Advances in Mathematics of Communications, vol. 2, no. 2, pp. 183–200, 2008.

[48] М. Саеди, М. С. Замани, М. Седиги и З. Сасанян
“Синтез обратимых схем с использованием подхода, основанного на циклах”,
Журнал ACM о новых технологиях в вычислительных системах, том 6, № 4, стр. 13, 2010.
[48] M. Saeedi, M. S. Zamani, M. Sedighi, and Z. Sasanian,
“Reversible circuit synthesis using a cycle-based approach,”
ACM Journal on Emerging Technologies in Computing Systems, vol. 6, no. 4, p. 13, 2010.

[49] Д. ГроБе, Р. Вилле, Г. У. Дуэк и Р. Дречслер
“Точный синтез элементарных квантовых вентильных схем",
Многозначная логика и программные вычисления, том 15, № 4, стр. 283-300, 2009.
[49] D. GroBe, R. Wille, G. W. Dueck, and R. Drechsler,
“Exact synthesis of elementary quantum gate circuits,”
Multiple-Valued Logic and Soft Computing, vol. 15, no. 4, pp. 283–300, 2009.

[50] Д. Маслов, Г. В. Дуэк и Д. М. Миллер
“Методы синтеза обратимых сетей Тоффоли",
ACM Trans. Дизайн Авто. Электр. Система, том 12, № 4, стр. 42, 2007.
[50] D. Maslov, G. W. Dueck, and D. M. Miller,
“Techniques for the synthesis of reversible Toffoli networks,”
ACM Trans. Design Autom. Electr. Syst., vol. 12, no. 4, p. 42, 2007.

[51] М. Сокен, Л. Таге, Г. У. Дуэк и Р. Дречслер
“Синтез больших обратимых функций без использования вспомогательных функций
с использованием диаграмм двоичных решений",
Журнал символических вычислений, том 73, стр. 1-26, 2016.
[51] M. Soeken, L. Tague, G. W. Dueck, and R. Drechsler,
“Ancilla-free synthesis of large reversible functions using binary decision diagrams,”
Journal of Symbolic Computation, vol. 73, pp. 1–26, 2016.

[52] М. Сокен, Г. У. Дуэк и Д. М. Миллер
“Алгоритм быстрого символьного преобразования, основанный на синтезе обратимой логики”,
в Международной конференции по обратимым вычислениям, 2016, стр. 307-321.
[52] M. Soeken, G. W. Dueck, and D. M. Miller,
“A fast symbolic transformation based algorithm for reversible logic synthesis,”
in Int’l Conf. on Reversible Computation, 2016, pp. 307–321.

[53] М. Сокен, Р. Вилле, О. Кешоче, Д. М. Миллер и Р. Дречслер
“Внедрение больших булевых функций для обратимой логики”,
Журнал ACM о новых технологиях в вычислительных системах,
том 12, № 4, стр. 41:1-41:26, 2016.
[53] M. Soeken, R. Wille, O. Keszocze, D. M. Miller, and R. Drechsler,
“Embedding of large Boolean functions for reversible logic,”
ACM Journal on Emerging Technologies in Computing Systems,
vol. 12, no. 4, pp. 41:1–41:26, 2016.

[54] А. Зуленер и Р. Вилле
“Сделайте это обратимым: продуктивное внедрение необратимых функций”,
в области проектирования, автоматизации и тестирования в Европе, 2017, стр. 458-463.
[54] A. Zulehner and R. Wille,
“Make it reversible: Efficient embedding of non-reversible functions,”
in Design, Automation and Test in Europe, 2017, pp. 458–463.

[55] М. Сокен, М. Реттелер, Н. Вибе и Г. Де Микели
“Автоматизация проектирования и исследование космического пространства для квантовых компьютеров”,
в "Проектирование, автоматизация и тестирование в Европе", 2017, стр. 470-475.
[55] M. Soeken, M. Roetteler, N. Wiebe, and G. De Micheli,
“Design automation and design space exploration for quantum computers,”
in Design, Automation and Test in Europe, 2017, pp. 470–475.

[56] К. Фазель, М. А. Торнтон и Дж. Э. Райс
“Каскадное поколение ворот Тоффоли на основе ESOP”,
на Конференции Тихоокеанского региона по связи, компьютерам и обработке сигналов, 2007.
[56] K. Fazel, M. A. Thornton, and J. E. Rice,
“ESOP-based Toffoli gate cascade generation,”
in Pacific Rim Conference on Communications, Computers and Signal Processing, 2007.

[57] А. Мищенко и М. А. Перковский
“Логический синтез обратимых волновых каскадов"
, на Международном семинаре по логике и синтезу, 2002.
[57] A. Mishchenko and M. A. Perkowski,
“Logic syntheis of reversible wave cascades,”
in Int’l Workshop on Logic and Synthesis, 2002.

[58] C. Бандьопадхай, Х. Рахаман и Р. Дречслер
“Улучшенный подход к сопряжению кубов на основе списка кубов
для синтеза обратимой логики на основе ESOP”,
Труды по вычислительной науке, том 24, стр. 129-146, 2014.
[58] C. Bandyopadhyay, H. Rahaman, and R. Drechsler,
“Improved cube list based cube pairing approach for synthesis of ESOP based reversible logic,”
Transactions on Computational Science, vol. 24, pp. 129–146, 2014.

[59] Р. Дречслер
“Выражения Преудо-Кронекера для симметричных функций",
IEEE Trans. о компьютерах, том 48, № 9, стр. 987-990, 1999.
[59] R. Drechsler,
“Preudo-Kronecker expressions for symmetric functions,”
IEEE Trans. on Computers, vol. 48, no. 9, pp. 987–990, 1999.

[60] А. Мищенко и М. А. Перковский
“Быстрая эвристическая минимизация исключительной суммы продуктов",
в мастерской Рида-Мюллера, 2001.
[60] A. Mishchenko and M. A. Perkowski,
“Fast heuristic minimization of exclusive-sum-of-products,”
in Reed-Muller Workshop, 2001.

[61] М. Сокен, Р. Вилле и Р. Дрехслер
“Иерархический синтез обратимых схем с использованием положительной и отрицательной декомпозиции Давио”,
в Международный симпозиум по проектированию и тестированию, 2010, стр. 143-148.
[61] M. Soeken, R. Wille, and R. Drechsler,
“Hierarchical synthesis of reversible circuits using positive and negative Davio decomposition,”
in Int’l Design and Test Symp., 2010, pp. 143–148.

[62] А. Чаттопадхай, А. Литтарру, Л. Г. Амар?, П.-Э. Гайардон и Г. Де Микели
“Обратимый логический синтез с помощью двоичных диаграмм решений с двоичными условиями”,
в Международный симпозиуме по многозначной логике, 2015, стр. 2-7.
[62] A. Chattopadhyay, A. Littarru, L. G. Amar?, P.-E. Gaillardon, and G. De Micheli
“Reversible logic synthesis via biconditional binary decision diagrams,”
in Int’l Symp. on Multiple-Valued Logic, 2015, pp. 2–7.

[63] М. Сокен и А. Чаттопадхай
“Повышение продуктивности и масштабируемости синтеза обратимой логики с использованием обычного логического синтеза”,
на конференции по автоматизации проектирования, 2016, стр. 149:1-149:6.
[63] M. Soeken and A. Chattopadhyay,
“Unlocking efficiency and scalability of reversible logic synthesis using conventional logic synthesis,”
in Design Automation Conference, 2016, pp. 149:1–149:6.

[64] Б. Валирон
“Генерация обратимых схем из функциональных программ более высокого порядка",
в Международная конференция по обратимым вычислениям, 2016, стр. 289-306.
[64] B. Valiron,
“Generating reversible circuits from higher-order functional programs,”
in Int’l Conf. on Reversible Computation, 2016, pp. 289–306.

[65] М. Сокен, М. Реттелер, Н. Вибе и Г. Де Микели
“Иерархический обратимый логический синтез с использованием LUTS”,
Конференция по автоматизации проектирования, 2017, стр. 78:1-78:6.
[65] M. Soeken, M. Roetteler, N. Wiebe, and G. De Micheli,
“Hierarchical reversible logic synthesis using LUTs,”
in Design Automation Conference, 2017, pp. 78:1–78:6.

[66] Р. Кралович
“Временная и пространственная сложность обратимой гальки”,
в Конф. о современных тенденциях в теории и практике информатики, 2001, стр. 292-303.
[66] R. Královic,
“Time and space complexity of reversible pebbling,”
in Conf. on Current Trends in Theory and Practice of Informatics, 2001, pp. 292–303.

[67] А. Парент, М. Реттелер и К. М. Своре
“Обороты: инструмент для синтеза обратимых схем с оптимизацией пространства”,
в Международной конференции по обратимым вычислениям, 2017, стр. 90-101.
[67] A. Parent, M. Roetteler, and K. M. Svore,
“REVS: A tool for spaceoptimized reversible circuit synthesis,”
in Int’l Conf. on Reversible Computation, 2017, pp. 90–101.

[68] М. Сокен, С. Фресе, Р. Вилле и Р. Дречслер
“RevKit: инструментарий для проектирования обратимых схем",
Многозначная логика и программные вычисления, том 18, № 1, стр. 55-65, 2012.
[68] M. Soeken, S. Frehse, R. Wille, and R. Drechsler,
“RevKit: A toolkit for reversible circuit design,”
Multiple-Valued Logic and Soft Computing, vol. 18, no. 1, pp. 55–65, 2012.

[69] М. Эми, Д. Маслов и М. Моска
“Оптимизация T-глубины в полиномиальное время схем Клиффорда+T
с помощью разбиения на матроиды",
IEEE Trans. о САПР интегральных схем и систем, том 33, № 10, стр. 1476-1489, 2014.
[69] M. Amy, D. Maslov, and M. Mosca,
“Polynomial-time T -depth optimization of Clifford+T circuits via matroid partitioning,”
IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 33, no. 10, pp. 1476–1489, 2014.

[70] М. Реттелер
“Квантовые алгоритмы для сильно нелинейных булевых функций",
на симпозиуме ACM-SIAM. о дискретных алгоритмах, 2010, с. 448-457.
[70] M. Roetteler,
“Quantum algorithms for highly non-linear Boolean functions,”
in ACM-SIAM Symp. on Discrete Algorithms, 2010, pp. 448–457.

[71] А. М. Чайлдс и У. ван Дам
“Квантовые алгоритмы для алгебраических задач",
Обзоры современной физики, том 82, № 1, стр. 1-52, 2010.
[71] A. M. Childs and W. van Dam,
“Quantum algorithms for algebraic problems,”
Reviews of Modern Physics, vol. 82, no. 1, pp. 1–52, 2010.

[72] С. Брави и Д. Госсет
“Улучшенное классическое моделирование квантовых схем,
в которых доминирует ворота Клиффорда”,
Письма о физическом обзоре, том 116, № 25, стр. 250501, 2016.
[72] S. Bravyi and D. Gosset,
“Improved classical simulation of quantum circuits dominated by Clifford gates,”
Physical Review Letters, vol. 116, no. 25, p. 250501, 2016.

[73] М. Эми, М. Реттелер и К. Своре
“Проверенная компиляция пространственно-продуктивных обратимых схем",
в Компьютерно-ассистированная верификация, 2017, стр. 3-21.
[73] M. Amy, M. Roetteler, and K. Svore,
“Verified compilation of spaceefficient reversible circuits,” in Computer Aided Verification, 2017, pp. 3–21.

© 2025 ❤ ANDREY KOVALEV w.f.a. ALLY ❤